/**
 *  Quick Sort
 *
 *  Time complexity: O(nlogn)
 *  Space complexity: O(1)
 *
 *  This algorithm only works if all numbers are unique!
 */

import java.util.Arrays;

class QuickSort {

    public static void sort(int[] a, int lo, int hi) {
        // Base case
        if (lo >= hi) return;
        
        // Partition operation
        int p = partition(a, lo, hi);

        sort(a, lo, p - 1);
        sort(a, p + 1, hi);
    }

    public static int partition(int[] a, int lo, int hi) {
        int left = lo;
        int right = hi;
        int v = a[left];

        while (left < right) {
            while (a[left] < v) left++;
            while (a[right] > v) right--;

            swap(a, left, right);
        }

        return left;
    }

    public static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

}
